1. Field of the Invention
The present invention relates to a half-pel searching method of a moving picture encoder, and more particularly, to a fast half-pel searching method for reducing calculation amount and calculation time. In the fast half-pel searching method of the present invention, half-pels are estimated and searched by using a stochastically selected value and SAD values of eight surrounding pixels used in searching for integer-pels to remove the necessity to access to a memory for integer-pel data, so that calculation amount and calculation time are reduced.
2. Description of the Related Art
Digital image data is generally used in video conference, a high fidelity Television, a video-on-demand (VOD) receiver, a moving picture experts group (MPEG) image supporting personal computer, a video game system, a digital ground wave broadcast system, a digital satellite broadcast system and a cable television (CATV). The digital image data is however not used as itself but is rather compressed by an efficient compression method because the data amount is greatly increased due to the characteristics of the image and the process for converting an analog signal into a digital signal.
Three compression methods are generally being used for the compression of digital image data. Mainly used are a method to reduce temporal redundancy, a method to reduce special redundancy and a compression method using stochastic properties of generation codes. The representative method to reduce temporal redundancy is the motion estimation and compensation method, which is being used in most moving picture compression standards such as MPEG, H.263, etc.
The motion estimation and compensation method is used to search for the most similar portion from a previous or next reference screen with respect to the particular portion of a current screen, and transmit only the difference components between the two portions. In the motion estimation and compensation method, the more finely motion vectors are searched, the more the amount of the difference components to be transmitted is reduced so that the amount of data is effectively reduced. However, to search the most similar portion from the previous or next screen, a large amount of estimation time and a calculation amount are required. Accordingly, it has been studied to reduce the motion estimation time that occupies the largest amount when the moving picture is encoded.
On the other hand, there are a pixel-by-pixel basis estimation method and a block-by-block basis estimation method as the motion estimation method. The block-by-block basis estimation method is the most popularly used representative algorithm.
In the block-by-block basis estimation method, image is divided into blocks of a predetermined size and the most matched block with the block of a current image is found in the search region of the current image. The difference between the found block and the current image block is called a motion vector. The motion vector is encoded and processed. Various match functions can be used for a match calculation of two blocks. The most popular function is the sum of absolute difference (SAD) value that is the sum of absolute values of differences of pixels between two blocks.
Thus, after the final integer-pel is obtained by integer-pel search, a better quality image is displayed through half-pel search in the moving picture standards such as MPEG-2 or more developed versions. In such a half-pel search, half-pels are calculated for eight pixels around the finally obtained integer-pel, the SAD values are obtained for the obtained half-pel blocks, and the half-pel having the smallest SAD value is searched.
However, in the conventional half-pel searching method, integer-pel data is used repeatedly and also the integer-pels have to be read at least four times randomly, it requires a calculation time at least four times as much as that required by the integer-pel searching method for one block. Since most of multimedia machines use SDRAM, when random memory access such as a half-pel search occurs, the half-pel search requires a considerable calculation time actually as a large amount of delay time is elapsed.
Therefore, the efficient implementation of the half-pel search, which is essentially included in the moving picture-related standards such as MPEG-2 or more developed versions, is the core in encoding the moving picture in real-time, and has been being researched and developed.